/*
https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/submissions/565529572/

二分搜索
24/9/14
*/

class Solution {
public:
    // 检查在给定的最大差值限制 `ops` 下，是否可以从 `nums` 中选出至少 `p` 对元素，使得每对元素的差值不超过 `ops`
    bool check(vector<int> &nums, int ops, int p) {
        int n = nums.size(); // 获取数组大小
        int ans = 0;         // 用于计数满足条件的对数

        // 贪心策略：从前往后尽可能选择满足条件的连续两个元素作为一对
        for (int i = 0; i < n && ans < p; i++) { // 只要还没有找到足够的对数就继续
            // 如果当前元素和下一个元素之间的差值小于等于 `ops`，则它们可以组成一对
            if (i + 1 < n && nums[i + 1] - nums[i] <= ops) {
                ans++; // 增加满足条件的对数
                i++;   // 跳过下一个元素，因为它已经被选入了一对
            }
        }

        // 如果找到了至少 `p` 对，则返回 true
        return ans >= p;
    }

    // 主函数，用于最小化最大差值
    int minimizeMax(vector<int>& nums, int p) {
        int n = nums.size(); // 获取数组大小
        sort(nums.begin(), nums.end()); // 对数组进行排序，以便于后续处理

        int l = 0, r = nums[n - 1]; // 初始化二分查找的左右边界，`r` 是数组中的最大值

        // 使用二分查找来确定最小的最大差值
        while (l <= r) {
            int mid = l + (r - l) / 2; // 计算中间值

            // 检查在 `mid` 作为最大差值限制时，是否可以选出至少 `p` 对
            bool flag = check(nums, mid, p);

            // 如果可以，则尝试更小的最大差值
            if (flag) {
                r = mid - 1;
            } else {
                // 否则，需要更大的最大差值
                l = mid + 1;
            }
        }

        // 最终 `l` 就是最小的最大差值
        return l;
    }
};